package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.StringTokenizer;

/**
 * 分析：
 * 实现：
 * 经验：
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1458WA {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1458WA.class.getResource("P1458.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		StringBuffer lines = new StringBuffer("");
		String line = stdin.readLine();
		while (line != null) {
			lines.append(" ").append(line);
			line = stdin.readLine();
		}
		
		StringBuffer sb = new StringBuffer("");
		StringTokenizer st = new StringTokenizer(lines.toString());
		while (st.hasMoreTokens()) {
			char[] a = st.nextToken().toCharArray();
			char[] b = st.nextToken().toCharArray();
			sb.append(common(a, b)).append("\n");
		}
		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb);
	}

	private static int common(char[] a, char[] b) {
		
		if (a.length > b.length) {
			return common(b, a);
		}

		int[] s = new int[a.length];
		s[0] = (a[0] == b[0])?1:0;
		for (int j = 1; j < a.length; j ++) {
			s[j] = (a[j] == b[0])?1:s[j-1];
		}
		int[] t = new int[a.length];
		for (int i = 1; i < b.length; i ++) {
			t[0] = (b[i] == a[0])?1:s[0];
			for (int j = 1; j < a.length; j ++) {
				t[j] = (b[i] == a[j])?(s[j-1]+1):Math.max(t[j-1], s[j]);
			}
			s = t;
		}
		return s[a.length-1];
	}
}